1. Field of the Invention
The present invention generally relates to methods for reproducing images by digital halftoning and, more particularly, to methods based upon digital halftoning with error diffusion.
2. State of the Art
In conventional halftone printing, picture elements (pixels) of a continuous-tone image are converted to dots whose diameters vary in size inversely with the color intensity of the corresponding area in the image. More particularly, the dots are larger where an image is darker and are smaller where an image is lighter, as shown in FIG. 1A of the accompanying drawings. Thus, conventional halftone printing processes can be described as an analog process because dot size is the analog of color intensity for individual picture elements of an original image.
To reproduce multi-color images from continuous-tone originals by conventional halftone printing, the original image is color filtered for each of four primary colors. Then the primary colors are printed sequentially while maintaining precise mechanical registration of the screens. If a scanned page is composed of several images and several text fields, those fields were mechanically stripped together to format the page.
By scanning images into a computer, the processes of page composition, image retouching and color correction can be made more flexible and more efficient. Such processes are commonly referred to as digital prepress processes. In these processes, an image is initially scanned with an optical scanner that detects intensity values for selected colors. Then, for each pixel location, the detected intensity data are converted to gray-scale values to provide a basis for image reproduction. Typically, gray-scale values are maintained in the computer by numbers that range from 0 to 255.
In digital halftone printing, dots are printed in areas that correspond with the original pixel locations. The printed dots normally are of fixed size, but their placement within the printed areas are varied in accordance with the detected gray-scale values. Thus, in images that have been produced by digital halftone printing, dot density within each printed area determines the spatial resolution and perceived color intensity (gray-scale value) of the area.
Conventional digital ,imaging subdivides an image into areas called super-cells. Within each super-cell, dots are clustered to form a dot pattern which is similar to that produced by the older analog process. (This is shown in FIG. 1-B of the accompanying drawings.) There are several shortcomings, however, in forming conventional digital dot patterns. One shortcoming, for example, is that visual interaction, referred to as moire patterns, can arise when dots are formed by the four or more printing inks. Avoidance of the moire patterns usually requires special digital processing techniques. Another shortcoming in forming conventional digital dot patterns is that the composite dot usually is much larger than the native dot of the image setting hardware. To overcome this shortcoming, it is usually required that the image setting equipment has high resolution (e.g., in the range of 2500 dots per inch) so that the image does not appear grainy or "noisy" and still have 256 gray scale values.
For purposes of reducing the grainy appearance of digital halftone images and for improving detail resolution, it has been suggested to use error diffusion techniques in conjunction with digital halftone printing. For example, Digital Halftoning, Robert Ulichney (MIT Press, 1987), 265-279, describes error diffusion techniques with perturbation. Such error diffusion techniques--sometimes referred to as stochastic screening or spatial dithering--produce a dot pattern similar to that shown in FIG. 1-C of the accompanying drawings. In that case, the dots are often said to be frequency modulated. When this process is performed for each of the primary printing colors, no special processing is required to prevent moire patterns.
To apply error diffusion techniques to digital halftone printing, gray-scale values at detected pixel locations are binary coded. The coding threshold usually is 127, i.e., halfway between the minimum and maximum gray-scale values. Then one binary number (e.g., 1) is assigned to pixel locations where detected gray-scale values are greater than 127, and another binary number (e.g., 0) is assigned to pixel locations where detected gray-scale values are 127 or less. Thus, for example, a pixel location with a detected gray-scale value of 100 would be coded as a binary "0" when binary coding for error diffusion in digital halftoning. Similarly, a pixel location with a gray-scale value of 145 would be coded as a binary "1" for this example. In monochrome printing systems based upon digital halftoning, a pixel location encoded as a binary "1" generally is black, and a pixel encoded as a binary "0" generally is white.
The above-described coding techniques for digital halftoning with error diffusion inherently result in coding errors. For example, the magnitude of the coding error resulting from binary encoding a pixel location having a gray-scale value of 100 would be 100 units away from zero units as measured by gray-scale values. Similarly, the magnitude of the coding error for binary encoding of a pixel location having a gray-scale value of 180 would be 75 units (the difference between 255 and 180) as measured by gray-scale values. There would, of course, be no coding errors for pixel locations having a gray-scale value of either 0 or 255, because those are the only two values that exactly correspond to the black and white dots, respectively.
The basic concept underlying digital halftone printing with error diffusion is to distribute, or diffuse, coding errors from the locations at which the errors arise. This concept is further discussed in an article, entitled "An Adaptive Algorithm for Spatial Grayscale", R. W. Floyd and L. Steinberg, Proc. SID, Vol. 17/2, pp. 75-77 (1976). Various algorithms have been proposed to accomplish error diffusion.
Although images produced by digital halftone printing with conventional error diffusion techniques may not have a grainy appearance, the printed images often contain discernible patterns. Such patterns are usually referred to as artifacts. Artifacts sometimes appear as straight lines and, other times, appear as wiggly or worm-like shapes. At still other times, artifacts have a random pebble-like appearance. Regardless of their particular form or shape, however, artifacts detract from the appearance of printed images and, therefore, limit the commercial acceptability of digital halftoning.
U.S. Pat. No. 5,051,841 to Bowers et al. provides an error diffusion process for reducing the occupance of visually-perceptible artifacts in images reproduced by digital halftone printing. According to the Bowers et al. patent, the error diffusion process includes the steps of, for selected pixel neighbors of the ith pixel in an image, diffusing the calculated error value E.sub.i of the ith pixel location to its selected neighbors as follows:
e.sub.j =(w.sub.j)E.sub.i
where e.sub.j is the error value diffused to the jth pixel neighbor from the ith pixel location, where the jth pixel neighbor is randomly determined from a predetermined set of pixels neighboring the ith pixel, and where w.sub.j is a weighting factor determined for the jth pixel location. E.sub.T, the total error to be diffused is defined as: ##EQU1##
One problem associated with these prior art methods is that the computations necessary for performing the process are computationally intensive and, therefore, time consuming. For instance, implementation of the process in the Bowers et al. patent involves floating point arithmetic in determining the error values for each of four neighboring pixels and diffusing the calculated errors in four directions. In practice, systems that used the Bowers et al. algorithm for error value calculations employed three RISC (Reduced Instruction Set Computer) accelerator processors, with each image being divided into three bands for separate processing, one band for each RISC processor.
The prior art error diffusion processes for digital halftone printing are complicated by the fact that each pixel in an image must be separately processed. For a typical image measuring 8,000 pixels by 10,000 pixels, the image would comprise 80,000,000 pixels. If each pixel in the image were are divided into three planes of color (corresponding to cyan, magenta, and yellow), then 240,000,000 pixels would have to be processed to reproduce the image. Thus, in this example, each error diffusion step would have to be executed 240,000,000 times.